Packet-based networks transport data in finite-length blocks, often called “packets”, “frames”, or “datagrams” in different contexts. A typical packet comprises a header and a payload. The header contains information about the packet's source and destination, and may contain other information that may be useful to devices along the packet's route such as time-stamps, priority information, flow control information, error-detection/correction checksums, etc. The payload contains the data to be delivered, and may include higher-level headers.
The job of a packet-based network is to deliver each packet from its source to its destination, efficiently, in a timely manner, and with as few lost packets as possible. Many of these packets will be handled during transit by routers and/or switches. Unless a data packet passes directly between its source device and destination device, such as might occur on a point-to-point connection, a modem-based circuit-switched connection, or a multiple-access collision-detection local area network (LAN), that packet will pass through at least one switch or router, and in some cases the packet will pass through many such devices.
Switches generally operate at layer two (the link layer) of a networking model. Routers generally operate at layer three (the network layer) of a networking model. For example, an Ethernet switch might read a layer two MAC (Media Access Control) header address on each incoming packet at one port, look up the MAC address in its forwarding table, and forward the packet out an appropriate port or ports towards that MAC address. An IP (Internet Protocol) router performs a similar function with IP destination addresses—the main functional difference being that the packets routed by the router are, in an Ethernet context, addressed to the router itself at layer 2. The router strips the layer 2 header, looks up the next-hop router for the layer 3 header, and prepends a new layer 2 header addressed to that next-hop router.
Behind the scenes, there can be other differences in routers and switches, e.g., how each populates its forwarding tables. For purposes of the present disclosure, however, these differences are not important. Thus the remainder of this disclosure will use the term “router” to refer to all multi-port packet devices capable of selectively forwarding packets to their output ports, regardless of the header layer used for the forwarding decision or how forwarding decisions get made.
All routers have external ports for receiving and transmitting packet data streams. Within the router, some packets may be dropped for various reasons, and some packets may be destined for the router itself and are therefore kept. The remainder of the packets are forwarded to one (or more) of the router's output ports according to a forwarding table lookup. For ten consecutive packets received at one port, each of those packets could conceivably be forwarded out a different output port; a different ten consecutive packets may all be forwarded out the same output port. Thus the core of the router, where packets actually get shuffled between ports, must be adaptive to changing traffic demands and adept at switching packets in order to avoid creating bottlenecks or unduly delaying some traffic.
Small routers may make all packet-forwarding decisions at a central location, e.g., a “forwarding engine” that touches each packet received by the router. As traffic load increases, the sheer number of packets that must be processed will overwhelm a single forwarding engine. Thus large routers often distribute forwarding tables to and make forwarding decisions at multiple forwarding engines, each assigned to certain ingress ports, egress ports, or both. FIG. 1 shows a simplified block diagram for one such router 20, and traces the path of two packets “ABC” and “PQR” through the router. Three forwarding engines 32, 42, and 52 serve three groups of input ports 30, 40, and 50, respectively. Each forwarding engine performs packet lookup for each packets arriving at its assigned input ports, and identifies the location where the packet should be sent. In this example, the location is one of the cell switch fabric output ports O0, O1, and O2. For instance, forwarding engine 32 receives packet ABC at one of input ports 30 and determines that the proper output port for packet ABC is one of ports 59. Forwarding engine 32 places a header or “tag” T on packet ABC so that the switch fabric can identify that packet with output port O2, and then transmits tagged packet TABC to port interface 34.
Port interface 34 places the packet in the format expected by switch fabric 22. Typically, switch fabric 22 operates on small, fixed-length “cells”, not variable-length packets. Thus port interface 34 divides the packet received from forwarding engine 34 into an appropriate number of cells for that packet's length, tags each cell with an identifier for output port O2, and submits the cells to switch fabric input port I0. In the example, port interface 34 divides tagged packet TABC into three sequential cells TA, TB, and TC.
Cell switch fabric 22 accepts cells from switch fabric input ports I0, I1, and I2, and switches those cells to output ports O0, O1, and O2, according to each cell's output port identifier. During switching of a layer packet, it is likely that cells from other input ports will contend for the same output port as cells TA, TB, and TC. For instance, port interface 54 has prepared three cells TP, TQ, and TR for transmission to output port O2. When those cells are presented to switch fabric 22 at approximately the same time as cells TA, TB, and TC, the cells from the two input ports may arrive at fabric output port O2 interleaved, as shown in FIG. 1. Port interface 56 has the job of sorting and rejoining the cells to reproduce packets TABC and TPQR.
Finally, egress switch 58 receives packets TABC and TPQR, looks at the respective tags T to determine the appropriate router output port for each, and prepares packets ABC and PQR for transmission out their respective ports 59.